SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Merge algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Merge algorithm</span></span>

</h1>

</header>

<p><b>Merge algorithms</b> are a family of <a href="Algorithm" title="Algorithm">algorithms</a> that take multiple <a href="Sorting_algorithm" title="Sorting algorithm">sorted</a> lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a> in various <a href="Sorting_algorithm" title="Sorting algorithm">sorting algorithms</a>, most famously <a href="Merge_sort" title="Merge sort">merge sort</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Application">Application</h2></div>

<p>The merge algorithm plays a critical role in the <a href="Merge_sort" title="Merge sort">merge sort</a> algorithm, a <a href="Comparison_sort" title="Comparison sort">comparison-based sorting algorithm</a>. Conceptually, the merge sort algorithm consists of two steps:

</p>

<ol><li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursively</a> divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of <i>n</i> elements as <i>n</i> sub-lists of size 1. A list containing a single element is, by definition, sorted.</li>

<li>Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list.</li></ol>

<p>The merge algorithm is used repeatedly in the merge sort algorithm.

</p><p>An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.

</p>

<div class="mw-heading mw-heading2"><h2 id="Merging_two_lists">Merging two lists</h2></div>

<p>Merging two sorted lists into one can be done in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a> and linear or constant space (depending on the data access model). The following <a href="Pseudocode" title="Pseudocode">pseudocode</a> demonstrates an algorithm that merges input lists (either <a href="Linked_list" title="Linked list">linked lists</a> or <a href="Array_data_structure" class="mw-redirect" title="Array data structure">arrays</a>) <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> into a new list <span class="texhtml mvar" style="font-style:italic;">C</span>.<sup id="cite_ref-skiena_1-0" class="reference"><a href="#cite_note-skiena-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-toolbox_2-0" class="reference"><a href="#cite_note-toolbox-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 104">: 104 </span></sup> The function <style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">head</span> yields the first element of a list; "dropping" an element means removing it from its list, typically by incrementing a pointer or index.

</p>

<pre><b>algorithm</b> merge(A, B) <b>is</b>

<b>inputs</b> A, B : list

<b>returns</b> list

C := new empty list

<b>while</b> A is not empty and B is not empty <b>do</b>

append head(A) to C

drop the head of A

append head(B) to C

drop the head of B

<i>// By now, either A or B is empty. It remains to empty the other input list.</i>

<b>while</b> A is not empty <b>do</b>

append head(A) to C

drop the head of A

<b>while</b> B is not empty <b>do</b>

append head(B) to C

drop the head of B

<b>return</b> C

</pre>

<p>When the inputs are linked lists, this algorithm can be implemented to use only a constant amount of working space; the pointers in the lists' nodes can be reused for bookkeeping and for constructing the final merged list.

</p><p>In the merge sort algorithm, this <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutine</a> is typically used to merge two sub-arrays <span class="monospaced">A[lo..mid]</span>, <span class="monospaced">A[mid+1..hi]</span> of a single array <span class="monospaced">A</span>. This can be done by copying the sub-arrays into a temporary array, then applying the merge algorithm above.<sup id="cite_ref-skiena_1-1" class="reference"><a href="#cite_note-skiena-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The allocation of a temporary array can be avoided, but at the expense of speed and programming ease. Various in-place merge algorithms have been devised,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> sometimes sacrificing the linear-time bound to produce an <span class="texhtml"><i>O</i>(<i>n</i> log <i>n</i>)</span> algorithm;<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> see <a href="Merge_sort#Variants" title="Merge sort">Merge sort § Variants</a> for discussion.

</p>

<div class="mw-heading mw-heading2"><h2 id="K-way_merging">K-way merging</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="K-way_merge_algorithm" title="K-way merge algorithm">K-way merge algorithm</a></div>

<p><span class="texhtml mvar" style="font-style:italic;">k</span>-way merging generalizes binary merging to an arbitrary number <span class="texhtml mvar" style="font-style:italic;">k</span> of sorted input lists. Applications of <span class="texhtml mvar" style="font-style:italic;">k</span>-way merging arise in various sorting algorithms, including <a href="Patience_sorting" title="Patience sorting">patience sorting</a><sup id="cite_ref-Chandramouli_5-0" class="reference"><a href="#cite_note-Chandramouli-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> and an <a href="External_sorting" title="External sorting">external sorting</a> algorithm that divides its input into <span class="texhtml"><i>k</i> = <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style><span class="sfrac">⁠<span class="tion"><span class="num">1</span><span class="sr-only">/</span><span class="den"><i>M</i></span></span>⁠</span> − 1</span> blocks that fit in memory, sorts these one by one, then merges these blocks.<sup id="cite_ref-toolbox_2-1" class="reference"><a href="#cite_note-toolbox-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 119–120">: 119–120 </span></sup>

</p><p>Several solutions to this problem exist. A naive solution is to do a loop over the <span class="texhtml mvar" style="font-style:italic;">k</span> lists to pick off the minimum element each time, and repeat this loop until all lists are empty:

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .framebox-container{margin-bottom:1.25em}.mw-parser-output .framebox-header{height:8px;margin:0;border:0;padding:0;font-size:1px}.mw-parser-output .framebox-inner{padding:5px;font-size:85%}

/* end https://en.wikipedia.org/ */

</style>

<ul><li>Input: a list of <span class="texhtml mvar" style="font-style:italic;">k</span> lists.</li>

<li>While any of the lists is non-empty:

<ul><li>Loop over the lists to find the one with the minimum first element.</li>

<li>Output the minimum element and remove it from its list.</li></ul></li></ul>

</div></div>

</div>

<p><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">In the worst case</a>, this algorithm performs <span class="texhtml">(<i>k</i>−1)(<i>n</i>−<span class="sfrac">⁠<span class="tion"><span class="num"><i>k</i></span><span class="sr-only">/</span><span class="den">2</span></span>⁠</span>)</span> element comparisons to perform its work if there are a total of <span class="texhtml mvar" style="font-style:italic;">n</span> elements in the lists.<sup id="cite_ref-greene_6-0" class="reference"><a href="#cite_note-greene-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

It can be improved by storing the lists in a <a href="Priority_queue" title="Priority queue">priority queue</a> (<a href="Heap_(data_structure)" title="Heap (data structure)">min-heap</a>) keyed by their first element:

</p>

<ul><li>Build a min-heap <span class="texhtml mvar" style="font-style:italic;">h</span> of the <span class="texhtml mvar" style="font-style:italic;">k</span> lists, using the first element as the key.</li>

<li>While any of the lists is non-empty:

<li>Output the first element of list <span class="texhtml mvar" style="font-style:italic;">i</span> and remove it from its list.</li>

<li>Re-heapify <span class="texhtml mvar" style="font-style:italic;">h</span>.</li></ul></li></ul>

</div></div>

</div>

<p>Searching for the next smallest element to be output (find-min) and restoring heap order can now be done in <span class="texhtml"><i>O</i>(log <i>k</i>)</span> time (more specifically, <span class="texhtml">2⌊log <i>k</i>⌋</span> comparisons<sup id="cite_ref-greene_6-1" class="reference"><a href="#cite_note-greene-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>), and the full problem can be solved in <span class="texhtml"><i>O</i>(<i>n</i> log <i>k</i>)</span> time (approximately <span class="texhtml">2<i>n</i>⌊log <i>k</i>⌋</span> comparisons).<sup id="cite_ref-greene_6-2" class="reference"><a href="#cite_note-greene-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-toolbox_2-2" class="reference"><a href="#cite_note-toolbox-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 119–120">: 119–120 </span></sup>

</p><p>A third algorithm for the problem is a <a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide and conquer</a> solution that builds on the binary merge algorithm:

</p>

<ul><li>If <span class="texhtml"><i>k</i> = 1</span>, output the single input list.</li>

<li>If <span class="texhtml"><i>k</i> = 2</span>, perform a binary merge.</li>

<li>Else, recursively merge the first <span class="texhtml">⌊<i>k</i>/2⌋</span> lists and the final <span class="texhtml">⌈<i>k</i>/2⌉</span> lists, then binary merge these.</li></ul>

</div></div>

</div>

<p>When the input lists to this algorithm are ordered by length, shortest first, it requires fewer than <span class="texhtml"><i>n</i>⌈log <i>k</i>⌉</span> comparisons, i.e., less than half the number used by the heap-based algorithm; in practice, it may be about as fast or slow as the heap-based algorithm.<sup id="cite_ref-greene_6-3" class="reference"><a href="#cite_note-greene-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Parallel_merge">Parallel merge</h2></div>

<p>A <a href="Task_parallelism" title="Task parallelism">parallel</a> version of the binary merge algorithm can serve as a building block of a <a href="Merge_sort#Parallel_merge_sort" title="Merge sort">parallel merge sort</a>. The following pseudocode demonstrates this algorithm in a <a href="Fork%E2%80%93join_model" title="Fork–join model">parallel divide-and-conquer</a> style (adapted from Cormen <i>et al.</i><sup id="cite_ref-clrs_7-0" class="reference"><a href="#cite_note-clrs-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 800">: 800 </span></sup>). It operates on two sorted arrays <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> and writes the sorted output to array <span class="texhtml mvar" style="font-style:italic;">C</span>. The notation <span class="monospaced">A[i...j]</span> denotes the part of <span class="texhtml mvar" style="font-style:italic;">A</span> from index <span class="texhtml mvar" style="font-style:italic;">i</span> through <span class="texhtml mvar" style="font-style:italic;">j</span>, exclusive.

</p>

<pre><b>algorithm</b> merge(A[i...j], B[k...ℓ], C[p...q]) <b>is</b>

<b>inputs</b> A, B, C : array

i, j, k, ℓ, p, q : indices

<b>let</b> m = j - i,

n = ℓ - k

swap A and B <i>// ensure that A is the larger array: i, j still belong to A; k, ℓ to B</i>

swap m and n

<b>return</b> <i>// base case, nothing to merge</i>

<b>let</b> r = ⌊(i + j)/2⌋

<b>let</b> s = binary-search(A[r], B[k...ℓ])

<b>let</b> t = p + (r - i) + (s - k)

C[t] = A[r]

<b>in parallel do</b>

merge(A[i...r], B[k...s], C[p...t])

merge(A[r+1...j], B[s...ℓ], C[t+1...q])

</pre>

<p>The algorithm operates by splitting either <span class="texhtml mvar" style="font-style:italic;">A</span> or <span class="texhtml mvar" style="font-style:italic;">B</span>, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The <a href="Binary_search" title="Binary search">binary search</a> subroutine returns the index in <span class="texhtml mvar" style="font-style:italic;">B</span> where <span class="texhtml"><i>A</i>[<i>r</i>]</span> would be, if it were in <span class="texhtml mvar" style="font-style:italic;">B</span>; that this always a number between <span class="texhtml mvar" style="font-style:italic;">k</span> and <span class="texhtml mvar" style="font-style:italic;">ℓ</span>.) Finally, each pair of halves is merged <a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">recursively</a>, and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <sup id="cite_ref-vjd_8-0" class="reference"><a href="#cite_note-vjd-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>The <a href="Analysis_of_parallel_algorithms#Overview" title="Analysis of parallel algorithms">work</a> performed by the algorithm for two arrays holding a total of <span class="texhtml mvar" style="font-style:italic;">n</span> elements, i.e., the running time of a serial version of it, is <span class="texhtml"><i>O</i>(<i>n</i>)</span>. This is optimal since <span class="texhtml mvar" style="font-style:italic;">n</span> elements need to be copied into <span class="texhtml mvar" style="font-style:italic;">C</span>. To calculate the <a href="Analysis_of_parallel_algorithms#Overview" title="Analysis of parallel algorithms">span</a> of the algorithm, it is necessary to derive a <a href="Recurrence_relation" title="Recurrence relation">Recurrence relation</a>. Since the two recursive calls of <i>merge</i> are in parallel, only the costlier of the two calls needs to be considered. In the worst case, the maximum number of elements in one of the recursive calls is at most <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {3}{4}}n}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {3}{4}}n}</annotation>

</semantics>

</math></span><img src="./03cdd03b9c94dc357866fff19b30d76b704a7cc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.053ex; height:3.509ex;" alt="{\textstyle {\frac {3}{4}}n}" loading="lazy"></span> since the array with more elements is perfectly split in half. Adding the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(\log(n)\right)}">

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(\log(n)\right)}</annotation>

</semantics>

</math></span><img src="./fe781b85fbecb5ad666c8633a9c44597e40e43a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.18ex; height:2.843ex;" alt="{\displaystyle \Theta \left(\log(n)\right)}" loading="lazy"></span> cost of the Binary Search, we obtain this recurrence as an upper bound:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}">

</mrow>

<mtext>merge</mtext>

</mrow>

</msubsup>

</mrow>

<mtext>merge</mtext>

</mrow>

</msubsup>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}</annotation>

</semantics>

</math></span><img src="./eae1486f7fdf8b173059cc917ef07035fe91b211.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:39.02ex; height:6.176ex;" alt="{\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}" loading="lazy"></span>

</p><p>The solution is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}">

</mrow>

<mtext>merge</mtext>

</mrow>

</msubsup>

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}</annotation>

</semantics>

</math></span><img src="./44290693b0162c2cc31186bf74e6ed618da209ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.105ex; height:3.343ex;" alt="{\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}" loading="lazy"></span>, meaning that it takes that much time on an ideal machine with an unbounded number of processors.<sup id="cite_ref-clrs_7-1" class="reference"><a href="#cite_note-clrs-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 801–802">: 801–802 </span></sup>

</p><p><b>Note:</b> The routine is not <a href="Sorting_algorithm#Stability" title="Sorting algorithm">stable</a>: if equal items are separated by splitting <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span>, they will become interleaved in <span class="texhtml mvar" style="font-style:italic;">C</span>; also swapping <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> will destroy the order, if equal items are spread among both input arrays. As a result, when used for sorting, this algorithm produces a sort that is not stable.

</p>

<div class="mw-heading mw-heading2"><h2 id="Parallel_merge_of_two_lists">Parallel merge of two lists</h2></div>

<p>There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays (<a href="FPGA" class="mw-redirect" title="FPGA">FPGAs</a>), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data (<a href="SIMD" class="mw-redirect" title="SIMD">SIMD</a>) instructions.

</p><p>Existing parallel algorithms are based on modifications of the merge part of either the <a href="Bitonic_sorter" title="Bitonic sorter">bitonic sorter</a> or <a href="Odd-even_mergesort" class="mw-redirect" title="Odd-even mergesort">odd-even mergesort</a>.<sup id="cite_ref-flimsj_9-0" class="reference"><a href="#cite_note-flimsj-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> In 2018, Saitoh M. et al. introduced MMS <sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <sup id="cite_ref-flimsj_9-1" class="reference"><a href="#cite_note-flimsj-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> that improved the hardware utilization and performance by only requiring <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(P)+1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(P)+1}</annotation>

</semantics>

</math></span><img src="./1a4cd0052e0b87fb5a7d81eeb4663fc7b8a711df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.584ex; height:2.843ex;" alt="{\displaystyle \log _{2}(P)+1}" loading="lazy"></span> pipeline stages of <span class="texhtml"><i>P/2</i></span> compare-and-swap units to merge with a parallelism of <span class="texhtml"><i>P</i></span> elements per FPGA cycle.

</p>

<div class="mw-heading mw-heading2"><h2 id="Language_support">Language support</h2></div>

<p>Some <a href="Computer_language" title="Computer language">computer languages</a> provide built-in or library support for merging sorted <a href="Collection_(abstract_data_type)" title="Collection (abstract data type)">collections</a>.

</p>

<p>The <a href="C%2B%2B" title="C++">C++</a>'s <a href="Standard_Template_Library" title="Standard Template Library">Standard Template Library</a> has the function <span class="monospaced">std::merge</span>, which merges two sorted ranges of <a href="Iterator" title="Iterator">iterators</a>, and <span class="monospaced">std::inplace_merge</span>, which merges two consecutive sorted ranges <i>in-place</i>. In addition, the <span class="monospaced">std::list</span> (linked list) class has its own <span class="monospaced">merge</span> method which merges another list into itself. The type of the elements merged must support the less-than (<span class="monospaced"><</span>) operator, or it must be provided with a custom comparator.

</p><p>C++17 allows for differing execution policies, namely sequential, parallel, and parallel-unsequenced.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Python">Python</h3></div>

<p><a href="Python_(programming_language)" title="Python (programming language)">Python</a>'s standard library (since 2.6) also has a <span class="monospaced">merge</span> function in the <span class="monospaced">heapq</span> module, that takes multiple sorted iterables, and merges them into a single iterator.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Merge_(revision_control)" class="mw-redirect" title="Merge (revision control)">Merge (revision control)</a></li>

<li><a href="Join_(relational_algebra)" title="Join (relational algebra)">Join (relational algebra)</a></li>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSkiena2010" class="citation book cs1"><a href="Steven_Skiena" title="Steven Skiena">Skiena, Steven</a> (2010). <i>The Algorithm Design Manual</i> (2nd ed.). <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer Science+Business Media</a>. p. 123. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-849-96720-4</bdi>.</cite></span>

</li>

<li id="cite_note-toolbox-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-toolbox_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-toolbox_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-toolbox_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFKurt_MehlhornPeter_Sanders2008" class="citation book cs1"><a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Kurt Mehlhorn</a>; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Peter Sanders</a> (2008). <a rel="nofollow" class="external text" href="http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/"><i>Algorithms and Data Structures: The Basic Toolbox</i></a>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-77978-0</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFKatajainenPasanenTeuhola1996" class="citation journal cs1">Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort". <i>Nordic J. Computing</i>. <b>3</b> (1): <span class="nowrap">27–</span>40. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523">10.1.1.22.8523</a></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFKimKutzner2004" class="citation conference cs1">Kim, Pok-Son; Kutzner, Arne (2004). <i>Stable Minimum Storage Merging by Symmetric Comparisons</i>. European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. <span class="nowrap">714–</span>723. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.4612">10.1.1.102.4612</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-30140-0_63">10.1007/978-3-540-30140-0_63</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-23025-0</bdi>.</cite></span>

</li>

<li id="cite_note-Chandramouli-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Chandramouli_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFChandramouliGoldstein2014" class="citation conference cs1">Chandramouli, Badrish; Goldstein, Jonathan (2014). <i>Patience is a Virtue: Revisiting Merge and Sort on Modern Processors</i>. SIGMOD/PODS.</cite></span>

</li>

<li id="cite_note-greene-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-greene_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-greene_6-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-greene_6-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-greene_6-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFGreene1993" class="citation conference cs1">Greene, William A. (1993). <a rel="nofollow" class="external text" href="http://www.cs.uno.edu/people/faculty/bill/k-way-merge-n-sort-ACM-SE-Regl-1993.pdf"><i>k-way Merging and k-ary Sorts</i></a> <span class="cs1-format">(PDF)</span>. Proc. 31-st Annual ACM Southeast Conf. pp. <span class="nowrap">127–</span>135.</cite></span>

</li>

<li id="cite_note-clrs-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-clrs_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-clrs_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFCormenLeisersonRivestStein2009" class="citation book cs1"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2009) [1990]. <a href="Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (3rd ed.). MIT Press and McGraw-Hill. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03384-4</bdi>.</cite></span>

</li>

<li id="cite_note-vjd-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-vjd_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFVictor_J._Duvanenko2011" class="citation cs2">Victor J. Duvanenko (2011), <a rel="nofollow" class="external text" href="http://www.drdobbs.com/parallel/parallel-merge/229204454">"Parallel Merge"</a>, <i>Dr. Dobb's Journal</i></cite></span>

</li>

<li id="cite_note-flimsj-9"><span class="mw-cite-backlink">^ <a href="#cite_ref-flimsj_9-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-flimsj_9-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFPapaphilippouLukBrooks2022" class="citation journal cs1">Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: a Fast Lightweight 2-way Merger for Sorting". <i>IEEE Transactions on Computers</i>: <span class="nowrap">1–</span>12. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2112.05607">2112.05607</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTC.2022.3146509">10.1109/TC.2022.3146509</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10044%2F1%2F95271">10044/1/95271</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:245669103">245669103</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFSaitohElsayedChuMashimo2018" class="citation book cs1">Saitoh, Makoto; Elsayed, Elsayed A.; Chu, Thiem Van; Mashimo, Susumu; Kise, Kenji (April 2018). "A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath". <i>2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)</i>. pp. <span class="nowrap">197–</span>204. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFCCM.2018.00038">10.1109/FCCM.2018.00038</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-5386-5522-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52195866">52195866</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://en.cppreference.com/w/cpp/algorithm/merge">"std:merge"</a>. cppreference.com. 2018-01-08<span class="reference-accessdate">. Retrieved <span class="nowrap">2018-04-28</span></span>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.python.org/library/heapq.html#heapq.merge">"heapq — Heap queue algorithm — Python 3.10.1 documentation"</a>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>. <i><a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a></i>, Volume 3: <i>Sorting and Searching</i>, Third Edition. Addison-Wesley, 1997. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89685-0</bdi>. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp. 197–207.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://duvanenko.tech.blog/2018/05/23/faster-sorting-in-c/">High Performance Implementation</a> of Parallel and Serial Merge in <a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a> with source in <a rel="nofollow" class="external text" href="https://github.com/DragonSpit/HPCsharp/">GitHub</a> and in <a href="C%2B%2B" title="C++">C++</a> <a rel="nofollow" class="external text" href="https://github.com/DragonSpit/ParallelAlgorithms">GitHub</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Sorting_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Sorting_algorithms231" style="font-size:114%;margin:0 4em"><a href="Sorting_algorithm" title="Sorting algorithm">Sorting algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computational_complexity_theory" title="Computational complexity theory">Computational complexity theory</a></li>

<li><a href="Big_O_notation" title="Big O notation">Big O notation</a></li>

<li><a href="Total_order" title="Total order">Total order</a></li>

<li><a href="List_(abstract_data_type)" title="List (abstract data type)">Lists</a></li>

<li><a href="In-place_algorithm" title="In-place algorithm">Inplacement</a></li>

<li><a href="Sorting_algorithm#Stability" title="Sorting algorithm">Stability</a></li>

<li><a href="Comparison_sort" title="Comparison sort">Comparison sort</a></li>

<li><a href="Adaptive_sort" title="Adaptive sort">Adaptive sort</a></li>

<li><a href="Sorting_network" title="Sorting network">Sorting network</a></li>

<li><a href="Integer_sorting" title="Integer sorting">Integer sorting</a></li>

<li><a href="X_%2B_Y_sorting" title="X + Y sorting">X + Y sorting</a></li>

<li><a href="Transdichotomous_model" title="Transdichotomous model">Transdichotomous model</a></li>

<li><a href="Quantum_sort" title="Quantum sort">Quantum sort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Exchange sorts</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bubble_sort" title="Bubble sort">Bubble sort</a></li>

<li><a href="Cocktail_shaker_sort" title="Cocktail shaker sort">Cocktail shaker sort</a></li>

<li><a href="Gnome_sort" title="Gnome sort">Gnome sort</a></li>

<li><a href="Proportion_extend_sort" title="Proportion extend sort">Proportion extend sort</a></li>

<li><a href="Quicksort" title="Quicksort">Quicksort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Selection_algorithm" title="Selection algorithm">Selection sorts</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Selection_sort" title="Selection sort">Selection sort</a></li>

<li><a href="Heapsort" title="Heapsort">Heapsort</a></li>

<li><a href="Smoothsort" title="Smoothsort">Smoothsort</a></li>

<li><a href="Cartesian_tree#Application_in_sorting" title="Cartesian tree">Cartesian tree sort</a></li>

<li><a href="Tournament_sort" title="Tournament sort">Tournament sort</a></li>

<li><a href="Cycle_sort" title="Cycle sort">Cycle sort</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Insertion sorts</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Insertion_sort" title="Insertion sort">Insertion sort</a></li>

<li><a href="Shellsort" title="Shellsort">Shellsort</a></li>

<li><a href="Splaysort" title="Splaysort">Splaysort</a></li>

<li><a href="Library_sort" title="Library sort">Library sort</a></li>

<li><a href="Patience_sorting" title="Patience sorting">Patience sorting</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Merge sorts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Merge_sort" title="Merge sort">Merge sort</a></li>

<li><a href="Cascade_merge_sort" title="Cascade merge sort">Cascade merge sort</a></li>

<li><a href="Oscillating_merge_sort" title="Oscillating merge sort">Oscillating merge sort</a></li>

<li><a href="Polyphase_merge_sort" title="Polyphase merge sort">Polyphase merge sort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Distribution sorts</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="American_flag_sort" title="American flag sort">American flag sort</a></li>

<li><a href="Bucket_sort" title="Bucket sort">Bucket sort</a></li>

<li><a href="Burstsort" title="Burstsort">Burstsort</a></li>

<li><a href="Counting_sort" title="Counting sort">Counting sort</a></li>

<li><a href="Interpolation_sort" title="Interpolation sort">Interpolation sort</a></li>

<li><a href="Pigeonhole_sort" title="Pigeonhole sort">Pigeonhole sort</a></li>

<li><a href="Proxmap_sort" title="Proxmap sort">Proxmap sort</a></li>

<li><a href="Radix_sort" title="Radix sort">Radix sort</a></li>

<li><a href="Flashsort" title="Flashsort">Flashsort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrent</a> sorts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bitonic_sorter" title="Bitonic sorter">Bitonic sorter</a></li>

<li><a href="Batcher_odd%E2%80%93even_mergesort" title="Batcher odd–even mergesort">Batcher odd–even mergesort</a></li>

<li><a href="Pairwise_sorting_network" title="Pairwise sorting network">Pairwise sorting network</a></li>

<li><a href="Samplesort" title="Samplesort">Samplesort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hybrid_algorithm" title="Hybrid algorithm">Hybrid sorts</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Block_sort" title="Block sort">Block merge sort</a></li>

<li><a href="Introsort" title="Introsort">Introsort</a></li>

<li><a href="Kirkpatrick%E2%80%93Reisch_sort" title="Kirkpatrick–Reisch sort">Kirkpatrick–Reisch sort</a></li>

<li><a href="Merge-insertion_sort" title="Merge-insertion sort">Merge-insertion sort</a></li>

<li><a href="Powersort" title="Powersort">Powersort</a></li>

<li><a href="Timsort" title="Timsort">Timsort</a></li>

<li><a href="Spreadsort" title="Spreadsort">Spreadsort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a>

<ul><li><a href="Pre-topological_order" title="Pre-topological order">Pre-topological order</a></li></ul></li>

<li><a href="Pancake_sorting" title="Pancake sorting">Pancake sorting</a></li>

<li><a href="Spaghetti_sort" title="Spaghetti sort">Spaghetti sort</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Impractical sorts</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stooge_sort" title="Stooge sort">Stooge sort</a></li>

<li><a href="Slowsort" title="Slowsort">Slowsort</a></li>

<li><a href="Bogosort" title="Bogosort">Bogosort</a></li>

<li><a href="Stalin_sort" title="Stalin sort">Stalin sort</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-18" href="https://en.wikipedia.org/wiki/?title=Merge_algorithm&oldid=1296233917">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>